A time division multiplexing (TDM) technology of accommodating signals of a large number of subscriber lines between telephone stations (buildings) is proposed. A transmission path that accommodates the signals of the subscriber lines on the basis of the TDM technology is referred to as a TDM transmission path. The signal of the subscriber line accommodated in the TDM transmission path is referred to as a traffic demand or demand. The demand specifies a route for a signal transmission from a starting point node to an ending point node. For example, a synchronous digital hierarchy (SDH) transmission path, an optical transport network (OTN) transmission path which has been standardized in recent years, or the like may be exemplified as the TDM transmission path.
When a demand is transmitted by using an optical fiber laid between telephone stations serving as nodes, signals of plural subscriber lines that may be transmitted through the same optical fiber are multiplexed in the TDM transmission path and transmitted. Optical fibers have been laid between adjacent telephone stations (nodes), and the TDM transmission path is set between a telephone station (node) on one end of an optical fiber and a telephone station (node) on the other end thereof. At this time, a mode in which one TDM transmission path passes through one optical fiber is typically adopted.
FIG. 1 illustrates an example including nodes, optical fibers, and TDM transmission paths. In the example of FIG. 1, a node A, a node B, a node C, a node D, and a node E are provided. Optical fibers are laid between the nodes A and B, between the nodes B and C, between the nodes C and D, and between the nodes D and E. The TDM transmission paths are set in four sections between the nodes A and B (#1), between the nodes B and C (#2), between the nodes C and D (#3), and between the nodes D and E (#4). At this time, for example, in a demand between the nodes A and E, the demand between the nodes A and B is accommodated in the TDM transmission path between the nodes A and B, the demand between the nodes B and C is accommodated in the TDM transmission path between the nodes B and C, the demand between the nodes C and D is accommodated in the TDM transmission path between the nodes C and D, and the demand between the nodes D and E is accommodated in the TDM transmission path between the nodes D and E. In this example, the demand between the nodes A and E is accommodated by an accommodating method offering this single set.
In recent years, a wavelength division multiplexing (WDM) technology has been introduced, and a device called an optical add/drop multiplexer (OADM) has been installed at the node. The OADM is an optical add/drop apparatus configured to perform add/drop or route switching of an optical signal in units of wavelength while keeping the optical signal. According to the WDM technology, as in related art, not only the TDM transmission path is set between adjacent nodes, but also the TDM transmission path may also be set between nodes that are not adjacent to each other since the optical signal passes through another node midway between the nodes while remaining as light.
FIG. 2 illustrates a configuration example of the OADM. When a wavelength-multiplexed optical signal is input from one optical fiber, the OADM illustrated in FIG. 2 demultiplexes the optical signal for each wavelength to be divided into light passing as it is, light to be dropped, and light to be added by an optical switch (optical SW). Furthermore, the OADM multiplexes optical signals for each wavelength to be output to the other optical fiber. The wavelength-multiplexed optical signal may also be input to the OADM from the other optical fiber.
FIG. 3 illustrates an example of the TDM transmission path. In the example of FIG. 3, the node A, the node B, the node C, the node D, and the node E are provided, and optical fibers (links) are laid between the nodes A and B, between the nodes B and C, between the nodes C and D, and between the nodes D and E similarly as in the example of FIG. 1. Herein, suppose that the OADM illustrated in FIG. 2 is arranged at the node B, the node C, and the node D in FIG. 1 (FIG. 3). In this case, in addition to the four sections of #1 to #4 illustrated in FIG. 1, the TDM transmission path may also be set in six sections between the nodes A and C (#5), between the nodes C and E (#6), between the nodes B and D (#7), between the nodes A and D (#8), between the nodes B and E (#9), and between the nodes A and E (#10) as illustrated in FIG. 3. According to this, the method of accommodating the demand between the nodes A and E differs from the above-mentioned accommodating method offering the single set.
FIG. 4 illustrates an example of a demand accommodating method. When the OADM illustrated in FIG. 2 is installed at the node B, the node C, and the node D in FIG. 1, the method of accommodating the demand between the nodes A and E has eight different sets as illustrated in FIG. 4. Specifically, the sets include a route using the TDM transmission paths of #1, #2, #3, and #4 (the same as the example in FIG. 1), a route using the TDM transmission paths of #5, #3, and #4, a route using the TDM transmission paths of #1, #2, and #6, and a route using the TDM transmission paths of #5 and #6. The sets further include a route using the TDM transmission paths of #1, #7, and #4, a route using the TDM transmission paths of #8 and #4, a route using the TDM transmission paths of #1 and #9, and a route using the TDM transmission path of #10. In this manner, with the introduction of the WDM technology, plural combinations of the TDM transmission paths used for accommodating one demand exist. An appropriate combination of the TDM transmission paths is desired to be selected while taking into account the accommodation of the other demands or the like with regard to respective demands.
For example, in a case where the OADM is installed at all the nodes on a certain network, it is assumed that the number of demands is K, and the number of nodes that a demand j (j=1, . . . , K) passes from a starting point to an ending point is nj inclusive of the starting point and the ending point. At this time, the number of combinations of the TDM transmission paths that accommodate the demand j is represented as follows.2nj−2 
Since the respective demands may select the combination of the TDM transmission paths to be accommodated independently of the other demands, the number of possible combinations for all the demands is represented as follows.2n1−2×2n2−2× . . . ×2nK−2 
Demands that select the TDM transmission path in the same section among the combinations of the TDM transmission paths selected for the respective demands may be multiplexed in the same TDM transmission path within a range of a capacity of the TDM transmission path. Therefore, the combination with which the number of TDM transmission paths for accommodating all the demands is minimized exists. As a method of obtaining this combination, mixed integer programming is proposed.
It is assumed that a capacity menu of the TDM transmission path is set as m. For example, m=1 represents a capacity of 8, and m=2 represents a capacity of 32. The capacity is equivalent, for example, to a circuit speed or a bit rate. It is also assumed that a number of TDM transmission path is set as h, and xm(h) denotes the number of TDM transmission paths h of the capacity menu m. costm denotes a cost of the TDM transmission path of the capacity menu m. An objective function for obtaining a minimal solution of the cost of the TDM transmission path by using this notation is represented as follows.
      minimize    ⁢          :        ⁢                  ∑        m                                      ⁢                          ⁢              {                              ∑            h                                                          ⁢                                          ⁢                                    cost              m                        ⁢                                          x                m                            ⁡                              (                h                )                                                    }                  (                  for        ⁢                                  ⁢                  ∀          m                    ,              ∀        h              )  
Next, constraints with regard to the demand will be described.
                    ∑        t                                      ⁢                          ⁢                        T          ⁡                      (                          l              ,              t                        )                          ·                  d          ⁡                      (            t            )                                =          numberOfDemands      ⁡              (        l        )                  (          for      ⁢                          ⁢              ∀        l              )  
Herein, T(l, t) is 1 when the combination candidate t of the TDM transmission paths may accommodate a demand l, and T(l, t) is 0 when the combination candidate t of the TDM transmission paths does not accommodate the demand l. The combination candidate of the TDM transmission paths is assigned with a number for demands having the same starting and ending points. For example, the combination candidate using the TDM transmission paths #1, #2, #3, and #4 in FIG. 4 is assigned such that l is 1. d(t) denotes the number of demands to be accommodated by the combination candidate t of the TDM transmission paths. numberOfDemands(l) denotes the number of the demands l. Therefore, the above-mentioned constraint means restrictions where the respective demands are to be accommodated by any one of the combinations of the TDM transmission paths.
Next, the capacity constraint for each TDM transmission path will be described.
                              ∑          t                                                ⁢                                  ⁢                  Demand_Cap          ⁢                                    (              t              )                        ·                          I              ⁡                              (                                  h                  ,                  t                                )                                      ·                          d              ⁡                              (                t                )                                                        -                        ∑          m                                                ⁢                                  ⁢                  TDM_CAP          ⁢                                    (              m              )                        ·                                          x                m                            ⁡                              (                h                )                                                          ≤    0        (          for      ⁢                          ⁢              ∀        h              )  
Demand_Cap(t) denotes a demand band with regard to a demand accommodation pattern t. The demand band is, for example, a bit rate per demand. I(h, t) is 1 in a case where the TDM transmission path h is included in the combination candidate t of the TDM transmission paths, and I(h, t) is 0 in a case where the TDM transmission path h is not included in the combination candidate t. For this reason, a first term of the expression represents a value obtained by multiplying the demand band by the number of demands to be accommodated in the demand accommodation pattern t with regard to the demand accommodation pattern t where the TDM transmission path h is included, that is, represents a total band of the demands accommodated in the TDM transmission path h. TDM_CAP(m) represents a capacity of the TDM transmission path of the capacity menu m. In the above-mentioned case, TDM_CAP(1) is 8 and TDM_CAP(2) is 32. A second term of the expression represents a total capacity of the TDM transmission path h of the capacity menu m. That is, the above-mentioned expression represents the condition that the total band of the demands accommodated in the TDM transmission path does not exceed the total capacity of the TDM transmission path.
Next, constraint on a wavelength number restriction of a link will be described. The link corresponds to an optical fiber between adjacent nodes.
                    ∑        h                                      ⁢                          ⁢              [                              Link            ⁡                          (                              s                ,                h                            )                                ·                      {                                          ∑                m                                                                              ⁢                                                          ⁢                                                x                  m                                ⁡                                  (                  h                  )                                                      }                          ]              ≤          Wavelength      ⁡              (        s        )                  (          for      ⁢                          ⁢              ∀        s              )  
Herein, Link(s, h) is 1 when the TDM transmission path h passes a link s, and Link(s, h) is 0 when the TDM transmission path h does not pass the link s. A left side of the expression represents the total number of TDM transmission paths that pass the link s. Wavelength(s) represents a wavelength number that may be utilized in the link s.
The number xm(h) of the respective TDM transmission paths may be obtained on the basis of the solution using the above-mentioned objective function and the three constraint expressions by the mixed integer programming. A solution method of the mixed integer programming has been proposed (for example, see Sakawa, Masatoshi, Optimization of Discrete Systems, Morikita Publishing, pp. 33-59, pp. 61-83, May, 2000). It is possible to carry out an appropriate network design by obtaining the minimum solution (optimal solution) in terms of the cost of the TDM transmission paths.
If the number of combination candidates of the TDM transmission paths that accommodate the demand is high, a range of a value that the demand accommodation pattern t may take is very wide, so that the expression of the mixed integer programming problem may be very large in some cases. If the expression becomes large, the calculation period of time is prolonged, and a vast storage area is also used, so that a case occurs that a general calculation facility such as a personal computer (PC) does not solve the problem. In addition, in a case where a search for all the possible combinations of the TDM transmission paths is conducted without using mathematical programming such as the mixed integer programming, it is difficult to solve the problem in a realistic period of time since the number of combination candidates of the TDM transmission paths is high. Therefore, to solve the problem in a realistic period of time, it is desirable to narrow down the combination candidates of the TDM transmission paths to those having a high probability of being the optimal solution.
For example, see Japanese Laid-open Patent Publication No. 2008-301225.